Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Інститут телекомунікацій, радіоелектроніки та електронної техніки
Кафедра теоретичної радіотехніки та радіовимірювань
Звіт з лабораторної роботи №11
Тема «Динамічні структури даних»
з дисципліни «Інформатика та обчислювальна техніка»
Мета роботи: вивчити способи створення динамічних структур даних (списків, стеків, дерев, тощо) та виконання операцій над ними.
Варіант 5
Постановка задачі. Утворити список, який містить інформацію згідно заданого варіанту. Кількість даних які вводяться визначаються в процесі вводу. Останій елемент повинен містити нулі в усіх полях. Після введення останнього елементу програма повинна вивести список на екран. Програма повинна містити функцію видалення елемента списку.
1. Згідно з індивідуальним завданням розробити необхідні структури даних.
2. Сформувати структури даних у динамічній пам’яті та проініціалізувати їх введеними з клавіатури значеннями. При відсутності в умові завдання наперед заданої кількості елементів спискових структур в якості ознаки завершення їх формування вибрати імітацію кінця файла клавіатурного введення (натискування клавіш Ctrl/Z), або ввести деяке обумовлене число чи символ.
3. Виконати над елементами списку операції перетворення (формування, включення, виключення, пошук, виведення елементів), необхідні для розв’язування задачі. Операції над списком оформити у вигляді окремих функцій.
4. Перед завершенням роботи програми звільнити виділену для списку динамічну пам’ять.
Завдання
Написати програму, яка вводить масив записів про студентів (Прізвище, ім’я, рік народження, група, рейтинг, стать). Програма повинна знайти і вивести на екран прізвища та ініціали студентів у яких рейтинг менший 50 балів.
Короткі теоретичні відомості
Список – це скінченний набір даних одного типу між якими налагоджено зв’язок. Елемент однонапрямленого списку складається з двох частин: самого даного та вказівника на наступний елемент списку.
Формат опису елементу списку:
struct назва_типу_списку
{
тип_поля1 назва_поля1;
тип_поля2 назва_поля2;
……………………………..
тип_поляN назва_поляN;
struct назва_типу_списку *тип_вказівника ;
}
Наприклад,
struct rika
{
char nazva[12];
int dov;
long int pl;
struct rika *dali;
}
В результаті опису списку отримують тільки шаблон типу даних. Для роботи зі списком потрібно оголосити необхідні вказівники. Формат оголошення вказівників:
struct назва_типу_списку *ім’я_вказівника1 … * ім’я _вказівникаМ;
Наприклад, struct rika *element, *pershyj, *poperednij, *novyj;
54
Вказівники *element, *pershyj, * poperednij, *novyj служать для організації роботи зі списком. Вказівник element – призначений для маркування поточного елементу списку. Тоді element-
>dov - вказівник на поле dov поточного елементу списку, element->dali - вказівник на наступний елемент списку, а element->dali->dov - вказівник на поле dov наступного елементу списку. Вказівник *pershyj призначений для маркування першого елементу списку, вказівник *poperednij - для маркування попереднього елементу списку, а *novyj – для елементу списку,
що створюється. На відміну від статичного масиву структур зв’язаний список є динамічним масивом структур. Створення нового елементу здійснюється наступним чином: novyj=(struct
rika*)malloc(sizeof(struct rika)).
Вилучення поточного елементу списку полягає в присвоїні вказівнику попереднього елементу вказівки на наступний за поточним елемент.
РОЗРОБКА АЛГОРИТМУ
Код програми мовою С
#include <stdio.h>
#include <stdlib.h>
struct sp
{
char priz[20];
char im[20];
int rik;
char gryp[20];
int rej;
char st[20];
struct sp *dali;
};
struct sp *el, *per, *pop, *nov;
int main(int argc, char *argv[])
{ int c=0,i,naj[20],kopija[20],sor;
puts("Vvedit dani pro stydentiv.");
puts("Dlja zakinch...
